The present invention relates generally to a method and apparatus for optimizing compilers by determining the maximum number of live registers used during the execution of a computer program.
Almost all microprocessors have a load-store architecture in which values are loaded from memory into registers, operations are performed on values loaded in the registers, and the resulting values are again stored into memory. Register allocation, which is typically a function of compilation systems, determines the values that may access the registers of a computer system during any point in the execution of a program. Accordingly, register allocation is an important technique of compiler optimization because the number of computer registers is limited and because register operations are performed faster than memory loads and stores. Register allocation is discussed with reference to Advanced Compiler Design and Implementation, Steven S. Myuchnick, 1997.
Some methods for optimizing register allocation limit the allocation of values to computer registers, to periods when an instruction associated with the value is live. It will be appreciated that a code instruction may be associated with a value, and the value is referred to as xe2x80x9clivexe2x80x9d during the time period in which the value may be executed. Also, the register accessed by the value is termed a xe2x80x9clive registerxe2x80x9d during the period that the value is live. The range of code instructions in which the value is live is referred to as a live range of the value. While a value is live it is desirable to allocate a register to the value to enable instruction processing to continue without storing the value in memory, and the allocated register may be referred to as a live register. Values may reside in virtual registers and virtual registers may represent hardware registers. As used herein the phrase computer registers, represents those registers that are visible to the software developer.
Prior register allocation solutions included recording a history of read instructions and write instructions and searching the recorded events to find the maximum number of live registers, sometimes referred to as the maximum pressure point, at a particular point in the execution of the program. Therefore, the comprehensive read instruction and write instruction history related to the execution of a program must be stored, and that results in a large amount of time required for compiler optimization. It will be appreciated by those skilled in the art, that compiler optimization uses the value of the maximum number of live registers to efficiently manager register allocation.
Since the number of samples to be searched is large, the associated large amount of computing resources and searching time has inhibited improvements in compiler optimization. As known to those skilled in the art, compiler optimization is solutions that increase the computer overhead necessary for compilation, reduce the usefulness of the optimization solution and reduce the productivity of software development engineers. This reduction in productivity and increase in computer system requirements has limited further improvement of software development techniques.
The present invention is a method and apparatus for determining the maximum number of live computer registers, or pressure point. Software developers typically follow a work cycle of development, debugging, and testing of code. The productivity of a software developer can be improved by reducing the time spent in any part of the development cycle. Development and debugging productivity primarily depends on compilation time. Therefore it is important to continue to create compiler optimization tools that improve the compilation process.
Accordingly it is an object of the invention to record the relevant events related to the execution of a computer program, as opposed to a comprehensive history of the read instructions and write instructions. That is, during the operation of the present embodiment events that do not affect the maximum number of live registers are not recorded.
It is also an object of the invention to maintain information about the maximum number of live registers for any partition related to the execution of a computer program. It will be understood that a partition may identify sub-sets of information related to the operation of the present invention.
It is also an object of the invention to reduce the overhead required to search the information related to execution of a computer program to determine the maximum number of live registers. Further, the present invention may bound the required system resources required to determine the maximum number of live registers to the number of registers associated with the number of partitions.
Accordingly, it is an object of the invention to improve software developer productivity by reducing the overhead required to search the information about execution to determine the maximum number of live registers.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.